import random

TARGET = 250
N = 5
all = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10
]
true_list = [1, 6, 6, 6, 6, 5]
false_list = [1, 1, 1, 1, 2, 2]
diff_list = [1, 2, 3, 4, 5, 6]

def gen(n: int):
    return random.sample(all, n)

class BackSolution():

    def cal2(self, x, y):
        result = set([x+y, x-y, y-x, x*y])
        if x != 0 and y % x == 0:
            result.add(y/x)
        if y != 0 and x % y == 0:
            result.add(x/y)
        return list(result)

    def get_2(self, input_cards: list):
        cards = input_cards[:]
        cards.sort()
        pairs = []
        d1 = []
        for card1 in cards[:]:
            if card1 in d1: 
                cards.pop(0)
                continue
            d1.append(card1)
            cards.pop(0)
            d2 = []
            for card2 in cards:
                if card2 in d2: continue
                d2.append(card2)
                left = input_cards[:]
                left.remove(card1)
                left.remove(card2)
                pairs.append({'pick': [card1, card2], 'left': left})
        return pairs
    
    def solution(self, input_cards):
        if len(input_cards) == 2:
            r = self.cal2(input_cards[0], input_cards[1])
            if TARGET in r:
                return True
            else:
                return False
        else:
            new_lists = self.get_2(input_cards)
            for list in new_lists:
                new_numbers = self.cal2(list['pick'][0], list['pick'][1])
                for n in new_numbers:
                    go_list = list['left'][:]
                    go_list.append(n)
                    result = self.solution(go_list)
                    if result:
                        return True
            return False
        
    def pcal2(self, x, y):
        # 1
        result = [{
            'detail': f'{x}+{y}={x+y}',
            'result': x+y
        }]
        existing = [x+y]
        # 2
        if x-y not in existing:
            result.append({
                'detail': f'{x}-{y}={x-y}',
                'result': x-y
            })
            existing.append(x-y)
        # 3
        if y-x not in existing:
            result.append({
                'detail': f'{y}-{x}={y-x}',
                'result': y-x
            })
            existing.append(y-x)
        # 4
        if x*y not in existing:
            result.append({
                'detail': f'{x}*{y}={x*y}',
                'result': x*y
            })
            existing.append(x*y)
        # 5
        if x!=0 and y%x==0 and y/x not in existing:
            result.append({
                'detail': f'{y}/{x}={y/x}',
                'result': y/x
            })
            existing.append(x*y)
        # 6
        if y!=0 and x%y==0 and x/y not in existing:
            result.append({
                'detail': f'{x}/{y}={x/y}',
                'result': x/y
            })
            existing.append(x/y)

        return result

    def pget_2(self, input_cards: list):
        cards = input_cards[:]
        cards.sort()
        pairs = []
        d1 = []
        for card1 in cards[:]:
            if card1 in d1: 
                cards.pop(0)
                continue
            d1.append(card1)
            cards.pop(0)
            d2 = []
            for card2 in cards:
                if card2 in d2: continue
                d2.append(card2)
                left = input_cards[:]
                left.remove(card1)
                left.remove(card2)
                pairs.append({'pick': [card1, card2], 'left': left})
        return pairs

    def psolution(self, input_cards, history):
        if len(input_cards) == 2:
            rr = self.pcal2(input_cards[0], input_cards[1])
            for r in rr:
                if r['result'] == TARGET:
                    history = history + ' ' + r['detail']
                    return True, history
            return False, history

        else:
            new_lists = self.pget_2(input_cards)
            for list in new_lists:
                new_numbers = self.pcal2(list['pick'][0], list['pick'][1])
                for n in new_numbers:
                    go_list = list['left'][:]
                    go_list.append(n['result'])
                    new_history = history + ' ' + n['detail']
                    result, newer_history = self.psolution(go_list, new_history)
                    if result:
                        return True, newer_history
            return False, newer_history

TEST = False

if TEST:
    s = BackSolution()
    timu = [3, 6, 7, 8]
    for _ in range(20):
        timu = gen(5)
        print(timu, end=' ')
        print(s.psolution(timu, ''))
else:
    from Solution import Solution
    ss1 = Solution()
    ss2 = BackSolution()
    for _ in range(20):
        timu = gen(5)
        r1 = ss1.answer(timu)
        r2 = ss2.solution(timu)
        if r1 != r2:
            print("Test Failed\nInput:", timu, "\nExpected:", r2, "\nGot:", r1)
            exit(1)
    exit(0)